#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> >convex_hull;     //convex_hull储存所有凸包点
void GetResult(vector<vector<int> > point, int x1, int y1, int x2, int y2)
{
    int i, x3, y3, R;
    int tmax;       //tmax：最远点在point中的索引
    int Rmax;       //Rmax：最远距离的值
    vector<vector<int> > result_pack; //存放上包点或者下包点
    
    result_pack.push_back({0});//上包点或者下包点计数，初始化为零

    x3 = point[1][0];
    y3 = point[1][1];
    R = x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3;
    Rmax = R;
    tmax = 1;
    if (R >= 0)
    {
        result_pack.push_back({ x3, y3 });       
        result_pack[0][0] = result_pack[0][0] + 1;
    }
    for (int i = 2; i <= point[0][0]; i++) //从点集的第二个点开始循环
    {
        x3 = point[i][0];
        y3 = point[i][1];
        R = x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3;
        if (R >= 0)     //如果R>=0，则是同一测包（上包或下包）的点
        {
            result_pack.push_back({ x3, y3 });
            result_pack[0][0] = result_pack[0][0] + 1;
        }
        if (R > Rmax)
        {
            Rmax = R;
            tmax = i;
        }
    } //找到一测距离直线最远的点的距离和索引
    if (Rmax <= 0)      //如果已经是边界点了
    {
        for (int i = 1; i <= result_pack[0][0]; i++)
        {
            x3 = result_pack[i][0];
            y3 = result_pack[i][1];
            R = x1 * y2 + x3 * y1 + x2 * y3 - x3 * y2 - x2 * y1 - x1 * y3;
            if (R == 0 && !((x3 == x2 && y3 == y2) || (x3 == x1 && y3 == y1))) //如果R是零并且这个新点不是决定直线的两个点，则加入凸包点集合
            {
                convex_hull.push_back({ result_pack[i][0], result_pack[i][1] });
                convex_hull[0][0] = convex_hull[0][0] + 1;
            }
        }
        return;
    }
    else
    {
        convex_hull.push_back({ point[tmax][0], point[tmax][1] });
        convex_hull[0][0] = convex_hull[0][0] + 1;
        if (result_pack[0][0] == 0)
            return;
    }
    GetResult(result_pack, x1, y1, point[tmax][0], point[tmax][1]);
    GetResult(result_pack, point[tmax][0], point[tmax][1], x2, y2);
}
int main(int argc, char** argv)
{
    vector<vector<int> > pointset = {{0}}; //pointset储存所有点
    int count = 1;      //整型变量conut用于计数
    int x1, y1, x2, y2, x3, y3; //三个点的坐标
    convex_hull.push_back({0}); //convex_hull的第一行第一列元素存放凸包点的个数，初始化为0

    cout << "===请输入所有点的坐标===" << endl;
    //初始化点集
    int x, y;
    while (count <= 10) //设置输入10个点
    {
        cout << "请输入点" << count << "的x轴坐标：" << endl;
        cin >> x;
        cout << "请输入点" << count << "的y轴坐标：" << endl;
        cin >> y;
        pointset.push_back({ x, y });
        count++;
    }
    //点集里一共有多少个点
    pointset[0][0] = count - 1;

    x1 = pointset[1][0];
    y1 = pointset[1][1];

    x2 = x1;
    y2 = y1;

    for (int i = 2; i <= pointset[0][0]; i++)
    {
        x3 = pointset[i][0];
        y3 = pointset[i][1];
        if (x3 < x1)
        {
            x1 = x3;
            y1 = y3;
        } //找到x最小的点赋给（x1, y1）
        else if (x3 > x2)
        {
            x2 = x3;
            y2 = y3;
        } //找到x最大的点赋给（x2, y2）
    }

    //两点是凸包点
    convex_hull.push_back({ x1, y1 });
    convex_hull.push_back({ x2, y2 });

    convex_hull[0][0] += 2;//凸包点个数加二

    /*因为新x1-x2和x2-x1符号相反，所以上包点和下包点对应的“计算距离公式分子绝对值内的数学表达式”的一正一负
    所以下面调换x1和x2顺序作为输入保证两者计算的“计算距离公式分子绝对值内的数学表达式”为正的情况各是上包点和下包点中的一种*/
    GetResult(pointset, x1, y1, x2, y2);
    GetResult(pointset, x2, y2, x1, y1);

    //打印
    cout << "\n\n构成凸包的点有：" << endl;
    for (int i = 1; i <= convex_hull[0][0]; i++)
    {
        cout << "(" << convex_hull[i][0] << ", " << convex_hull[i][1] << ")" << endl;
    }
}
